package BinaryTree;

public class MaxDistance {

    /**
     * 求二叉树的最大距离
     * curr当前节点
     * 1. 跟curr无关， max（左子树的最大距离，右子树的最大距离）
     * 2. 跟curr有关， max(max（左子树的最大距离，右子树的最大距离）, 左子树高度+右子树高度+1)
     * **/

    public Info process(TreeNode root) {
        if (root == null)
            return new Info(0, 0);

        Info left = process(root.left);
        Info right = process(root.right);

        int height = Math.max(left.height, right.height) + 1;

        int maxDistance = Math.max(Math.max(left.maxDistance, right.maxDistance), left.height + right.height + 1);

        return new Info(maxDistance, height);
    }


    class Info {
        public int maxDistance;
        public int height;

        public Info(int dist, int h) {
            maxDistance = dist;
            height = h;
        }
    }

}
